package LingShen.GreedyAlgorithm;

/*
洛谷
P1809 过河问题
很有意思的贪心题
题目描述
有一个大晴天，Oliver 与同学们一共 N 人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。
船太小了，一次只能乘坐两人。每个人都有一个渡河时间 T，船划到对岸的时间等于船上渡河时间较长的人所用时间。
现在已知 N 个人的渡河时间 T，Oliver 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。
注意，只有船在东岸（西岸）的人才能坐上船划到对岸。

输入格式
输入文件第一行为人数 N，以下有 N 行，每行一个数。
第 i+1 行的数为第 i 个人的渡河时间。
输出格式
输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间。
输入输出样例
输入 #1
4
6
7
10
15
输出 #1
42

 */
public class P1809过河问题 {

    //题解：C语言
    //局部最优解 思考的方向在 当过河人数n大于3的时候，每次将最慢的两人组送入河对岸的最短时间是多少
    //1.最快的人反复过去将最慢的两个依次送过去                  即： a[1]*2+a[n]+a[n-1]
    //2.最快的两人组先过去,然后依次回来,让最慢的两人组一起过去     即： a[1]+a[2]*2+a[n]    思路：当a[n-1]的越大越接近a[n]节省的时间越多
    /*
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>

    using namespace std;

    int i,n,a[100010];
    long long ans;

    void re(int &x)//快读
    {
        x=0;
        char ch=getchar();
        while(ch<'0'||ch>'9')ch=getchar();
        while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    }

    bool cmp(const int x,const int y)
    {
        return x<y;
    }

    int main()
    {
        re(n);
        for(i=1;i<=n;i++)
            re(a[i]);
        sort(a+1,a+n+1,cmp);//按用时由小到大排序
        while(n>3)
        {
            ans+=min(a[1]*2+a[n]+a[n-1],a[1]+a[2]*2+a[n]);//根据公式累加
            n-=2;//每次此岸人数减少2人
        }
        if(n==2) ans+=a[2];//此岸人数n为2或3时
        if(n==3) ans+=a[1]+a[2]+a[3];
        printf("%lld",ans);
        return 0;
    }
    */
}
